/*
https://leetcode-cn.com/problems/remove-invalid-parentheses/solution/shan-chu-wu-xiao-de-gua-hao-by-leetcode-9w8au/
 */
import java.util.*;

public class Solution301 {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans=new ArrayList<>();
        Set<String> deal=new HashSet<>();
        Queue<String> queue=new ArrayDeque<>();
        queue.offer(s);
        int result=-1;
        while (true){
            if (queue.isEmpty()){
                break;
            }
            String target=queue.poll();
            if (target.length()<result){
                break;
            }
            if (isValid(target)){
                result=target.length();
                ans.add(target);

            }
            for (int i=0;i<target.length();i++){
                if (target.charAt(i)=='('||target.charAt(i)==')'){
                    String newS=target.substring(0,i).concat(target.substring(i+1));
                    if (!deal.contains(newS)) {
                        queue.offer(newS);
                        deal.add(newS);
                    }
                }
            }
        }
        return ans;
    }

    public boolean isValid(String s){
        int count=0;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='('){
                count++;
            }
            if (s.charAt(i)==')'){
                count--;
                if (count<0){
                    return false;
                }
            }
        }
        return count==0?true:false;
    }
    public static void main(String[] args) {
        System.out.println(new Solution301().removeInvalidParentheses("()())()"));
    }
}
